package LeetCode刷题;

import java.util.Stack;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-09-22 15:41
 * @description: Functions of this class is
 *
 * 给定一个只包括 *'('40，')'41，*'{'123，'}'125，*'['90，']'92 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：***
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 **/
public class NoNo有效括号 {
    /**
     * 遍历字符串+辅助栈
     */
    public static void main(String[] args) {
        System.out.println(isValid("(){}}{"));
        // "()[]{}" true
        // "(}){" false
        // "{[]}" true
    }
    public static boolean isValid(String s) {
        if(s.length()%2==1||(s.charAt(0)=='}')||(s.charAt(0)==']')||(s.charAt(0)==')')) {//鲁棒
            //长度奇数的、开头就是右括号的字符串直接判负
            return false;
        }
        Stack<Character>stack=new Stack<>();
        stack.push(s.charAt(0));//先把第一个字符入栈
        for(int i=0;i<s.length()-1;i++){
            char c=s.charAt(i+1);//从第二个字符开始判断
            if(c=='('||c=='{'||c=='['){//如果仍旧是左括号的话，在进行入栈
                stack.push(c);
            }
            else {//如果遇到了方向向右的括号
                if(stack.empty()&&i<s.length()-1){//判断下当前栈是否为空，为空直接返回假
                    return false;
                }
                char cc=stack.pop();//推出栈顶的元素进行判断
                //如果从栈中弹出的元素和目前的元素不能成为一对完整括号的话，返回假
                if((cc=='('&&c!=')')||((cc=='{'&&c!='}'))||((cc=='['&&c!=']'))){
                    return false;
                }
            }
        }
        return stack.empty();//字符串判断完毕,如果当前栈为空，说明字符串都符合括号开闭要求，返回真
    }
}